package com.hw3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ParseExpression2 {
	
	public static List<String> stringTokenizer(String input){
        int len=input.length();
        List<String> inp=new ArrayList<String>();
        for(int i=0,j=0;i<len;i++){
            if(i+1!=len && ((input.charAt(i)-'0'<10 && input.charAt(i)-'0'>=0) || input.charAt(i)=='.') && 
                    ((input.charAt(i+1)-'0'<10 && input.charAt(i+1)-'0'>=0) || input.charAt(i+1)=='.')){
                continue;
            }
            else{
                inp.add(input.substring(j,i+1));
                j=i+1;
            }
        }
        return inp;
    }
    
    /*
     * exp=terp {+- term}
     * term=term2 {x/term2}
     * term2=(exp)|number
     */
    public static Double solveExpression(List<String> token){
		Double value=solveTerm(token);
		while(!token.isEmpty() && (token.get(0).equals("+") || token.get(0).equals("-"))){
			String op=token.remove(0);
			if(op.equals("+")){
				value=value+solveTerm(token);
			}
			else{
				value=value-solveTerm(token);
			}
		}
		return value;
	}
	
	public static Double solveTerm(List<String> token){
		Double value=solveTerm2(token);
		while(!token.isEmpty() && (token.get(0).equals("*") || token.get(0).equals("/"))){
			String op=token.remove(0);
			if(op.equals("*")){
				value=value*solveTerm2(token);
			}
			else{
				value=value/solveTerm2(token);
			}
		}
		return value;
	}
	
	public static Double solveTerm2(List<String> token){
		Double value;
		if("(".equals(token.get(0))){
			token.remove(0);
			value=solveExpression(token);
			token.remove(0);
		}
		else if("-".equals(token.get(0))){
			token.remove(0);
			value=-Double.parseDouble(token.remove(0));
		}
		else{
			value=Double.parseDouble(token.remove(0));
		}
		return value;
	}
	
	public static Double recursiveDescent(String s){
		List<String> inp=stringTokenizer(s);
        Double value=solveExpression(inp);
        return value;
	}
	public static void testResursiveDescent(){
        String s="1+(20.7*3)-7/(7-5)";
        System.out.println(recursiveDescent(s));
    }
	
	/*
     * exp(p)=term {+- exp(q)}
     * exp(q)=(exp(q))|number
     */
	
	public static Map<String,Integer> getPrecedenceMap(){
        Map<String,Integer> pre=new HashMap<String,Integer>();
        String[] operator={"^","/","*","+","-"};
        /*for(int i=0;i<operator.length;i++){
            pre.put(operator[i], operator.length-i);
        }*/
        pre.put("/", 2);
        pre.put("*", 2);
        pre.put("+", 1);
        pre.put("-", 1);
        pre.put("=", 0);
        
        return pre;
    }
	
	
	public static Object precedenceClimbing(String inp){
		//solve AST and return boolean or double
		List<String>token=stringTokenizer(inp);
		Map<String, Integer> map=getPrecedenceMap();
		ASTNode root=solveExpression(token,0,map);
		if(root.getUsesEqual()){
			return root.getIsEqual();
		}
		return root.getValue();
		
		
	}

	private static Object getOperationValue(Double first, Double last,String operatr) {
        switch (operatr){
            case "+":return first+last;
            case "/":return first/last;
            case "*":return first*last;
            case "-":return first-last;
            case "^":return Math.pow(first, last);
            case "=":return (first.doubleValue()==last.doubleValue());
        }
        return null;
    }
	
	private static ASTNode solveExpression(List<String> token, int pre,Map<String,Integer>map) {
		ASTNode l=solveTerm(token,pre,map);
		ASTNode par=null;
		while(!token.isEmpty() && map.containsKey(token.get(0)) && (map.get(token.get(0))>=pre)){
			int q=map.get(token.get(0))+1;//only left associativity/no exp
			par=new ASTNode();
			//remove token as it is consumed
			par.setOp(token.get(0));
			token.remove(0);
			par.setLeft(l);
			par.setRight(solveExpression(token,q,map));
			//update value of parent node
			if("=".equals(par.getOp())){
				boolean val=(boolean)getOperationValue(par.getLeft().getValue(), par.getRight().getValue(), par.getOp());
				par.setUsesEqual(true);
				par.setValue(l.getValue());
				par.setIsEqual(val);
				if(!val)
					return par;
			}
			else{
				Double val=(Double)getOperationValue(par.getLeft().getValue(), par.getRight().getValue(), par.getOp());
				par.setValue(val);
			}
			
			l=par;
		}
		
		return l;
	}
	
    private static ASTNode solveTerm(List<String> token, int pre,Map<String,Integer>map) {
    	ASTNode t=new ASTNode();
		String op=token.remove(0);
		if("(".equals(op)){
			t=solveExpression(token,0,map);
			token.remove(0);
			return t;
		}
		else if("-".equals(op)){
			t.setValue(-Double.parseDouble(token.remove(0)));
			return t;
		}
		else{
			t.setValue(Double.parseDouble(op));
			return t;
		}
		
	}
    
    public static void testPrecedenceClimbing(){
    	String[] inp={"1+2*3/(7-5)-2+4*3+(3-3*7)/(6*0.5)-45.45*3-(22-45)/3*(8)",
    			"(22-44)*7/5*3*4/5/11",
    			"-43+7*12.5/-4+8",
    			"7-21=-2*7=14-28"
    	};
    	
    	/*String inp="(22-45)/3*(8)";
    	Double val3=(22.5-45)/3*(8);*/
    	for (int i=0;i<inp.length;i++) {
    		String input=inp[i];
    		Object val=precedenceClimbing(input);
        	//Double val2=recursiveDescent(input);
        	//System.out.println(val+","+val2);
        	System.out.println(val);
		}
    	
    }
}
